// Thor - High Performance C++ containers and algorithm library.
//
// Copyright (c) 2010 Su Shi. All rights reserved.
//
// Author: Su Shi <carmack.shi [at] gmail.com>

#include <set>
#include <map>
#include <algorithm>

#include <thor_geometry.h>

using ::std::vector;

namespace thor {

namespace geom {

//typedef std::vector<std::vector<size_t>> SegmentList;
//typedef std::pair<Point2d, SegmentList> Event;
//typedef std::map<Event::first_type, Event::second_type, PriorityCompare>
//    EventQueue;
//
//CircularArc2d::CircularArc2d(const Point2d& start_pt, const Point2d& mid_pt,
//                             const Point2d& end_pt)
//  : Segment2d(start_pt, end_pt), mid_pt_(mid_pt) {
//}

bool Segment2dCompare::operator ()(const Segment2d& lhs,
                                   const Segment2d& rhs) const {
  double coord_x = set_.scan_position();

  if (lhs.EvaluateY(coord_x) == rhs.EvaluateY(coord_x)) {
    if (lhs.Slope() == rhs.Slope()) {
      if (lhs.lower_x() == rhs.lower_x()) {
        return lhs.upper_x() < rhs.upper_x();
      } else {
        return (lhs.lower_x() < rhs.lower_x());
      }
    } else {
      return (lhs.Slope() < rhs.Slope());
    }
  } else {
    return (lhs.EvaluateY(coord_x) < rhs.EvaluateY(coord_x));
  }
}

void MutableSegment2dSet::Reorder() {
  iterator first = begin();
  iterator last;
  iterator end = this->end();

  while (first != end)
  {
    last = GetIntersectingSegments(first, end);
    if (std::distance(first, last) > 1)
    {
      Reverse(first, last);
    }
    first = last;
  }
}

void MutableSegment2dSet::Reverse(iterator first, iterator last) {
  std::reverse(first, last);
}

MutableSegment2dSet::iterator
MutableSegment2dSet::GetIntersectingSegments(
    MutableSegment2dSet::iterator first, MutableSegment2dSet::iterator end) {
    MutableSegment2dSet::iterator last = first;
    ++last;
    while (last != end && last->Slope() != first->Slope() &&
           first->EvaluateY(scan_position_x_) ==
              last->EvaluateY(scan_position_x_))
      ++last;

    return last;
}

// Use a sweep line from left to right.
std::vector<Point2d> FindIntersections(const std::vector<Segment2d>& segments) {
  assert(segments.size() > 1);
  std::set<double> scan_set;

  // Generate X coordinate for scanning line moving.
  for (size_t i = 0; i < segments.size(); ++i) {
    scan_set.insert(segments[i].start_point().x);
    scan_set.insert(segments[i].end_point().x);
  }

  MutableSegment2dSet active_segments;

  while (scan_set.size > 0) {
    // Get the new scan line's X-coordinate.
    std::set<double>::iterator it = scan_set.begin();
    double coord_x = *it;
    scan_set.erase(it);

    // Reorder each segment in the segment with new coordinate x.
    active_segments.Reorder(coord_x);

    // For each segment in the given set, we'll find the segment whose [left]
    // endpoint is the intersection point of scanning line and this segment.
    for (size_t i = 0; i < segments.size(); ++i) {
      if (segments[i].lower_x() == coord_x) {
        std::pair<MutableSegment2dSet::iterator, bool> ret =
            active_segments.insert(segments[i]);
        if (ret.second) {
          MutableSegment2dSet::iterator pre = ret.first;
          --pre;
          // If pre is valid, we should try to find intersection point between
          // pre & ret.first. Then we should put these intersection point into
          // scanning set.

          MutableSegment2dSet::iterator post = ret.first;
          ++post;
          // If post is valid, we should try to find intersection point between
          // post & ret.first. Then we should put these intersection point into
          // scanning set.
        }
      }
    }


    // For each segment in the active segment set
  }
}



}  // geom

}  // thor